package org.example.Soution001;

import java.util.ArrayList;
import java.util.List;

public class Permutations {
    //回溯-全排列
    public static void main(String[] args) {
        Permutations p = new Permutations();
        int[] arr=new int[] {};
        List<List<Integer>> result = p.permute(arr);
        System.out.println(result);
    }

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> firstList=new ArrayList<>();
        if(nums.length==0){
            return firstList;
        }
        List<Integer> allNumbers=new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            allNumbers.add(nums[i]);
        }
        List<List<Integer>> remainList=new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            List<Integer> tempList=new ArrayList<>();
            tempList.add(nums[i]);
            firstList.add(tempList);
            List<Integer> tempList2=new ArrayList<>(allNumbers);
            tempList2.remove(i);
            remainList.add(tempList2);
        }
        return getResult(firstList,remainList);
    }

    public List<List<Integer>> getResult(List<List<Integer>> firstList,List<List<Integer>> remainList) {
        if(remainList.get(0).size()==0){
            return firstList;
        }
        List<List<Integer>> resultList=new ArrayList<>();
        List<List<Integer>> stillRemain=new ArrayList<>();
        int num1=remainList.size();
        int num2=remainList.get(0).size();
        for(int i=0;i<num1;i++){
            for(int j=0;j<num2;j++){
                List<Integer> tempList=new ArrayList<>(firstList.get(i));
                tempList.add(remainList.get(i).get(j));
                resultList.add(tempList);
                List<Integer> tempList2=new ArrayList<>(remainList.get(i));
                tempList2.remove(remainList.get(i).get(j));
                stillRemain.add(tempList2);
            }
        }
        return getResult(resultList,stillRemain);
    }
}
